package com.sheng.leetcode.year2024.month08.day15;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author by ls
 * @date 2024/8/15
 * <p>
 * 3148. 矩阵中的最大得分<p>
 * <p>
 * 给你一个由 正整数 组成、大小为 m x n 的矩阵 grid。你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）。从值为 c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1 。<p>
 * 你可以从 任一 单元格开始，并且必须至少移动一次。<p>
 * 返回你能得到的 最大 总得分。<p>
 * <p>
 * 示例 1：<p>
 * 输入：grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]<p>
 * 输出：9<p>
 * 解释：从单元格 (0, 1) 开始，并执行以下移动：<p>
 * - 从单元格 (0, 1) 移动到 (2, 1)，得分为 7 - 5 = 2 。<p>
 * - 从单元格 (2, 1) 移动到 (2, 2)，得分为 14 - 7 = 7 。<p>
 * 总得分为 2 + 7 = 9 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：grid = [[4,3,2],[3,2,1]]<p>
 * 输出：-1<p>
 * 解释：从单元格 (0, 0) 开始，执行一次移动：从 (0, 0) 到 (0, 1) 。得分为 3 - 4 = -1 。<p>
 * <p>
 * 提示：<p>
 * m == grid.length<p>
 * n == grid[i].length<p>
 * 2 <= m, n <= 1000<p>
 * 4 <= m * n <= 10^5<p>
 * 1 <= grid[i][j] <= 10^5<p>
 */
public class LeetCode3148 {

    @Test
    public void test01() {
//        int[][] ints = {{9, 5, 7, 3}, {8, 9, 6, 1}, {6, 7, 14, 3}, {2, 5, 3, 1}};
        int[][] ints = {{4, 3, 2}, {3, 2, 1}};
        List<List<Integer>> grid = Arrays.stream(ints).map(i -> Arrays.stream(i).boxed().collect(Collectors.toList())).collect(Collectors.toList());
        System.out.println(new Solution().maxScore(grid));
    }
}

class Solution {
    public int maxScore(List<List<Integer>> grid) {
        int m = grid.size();
        int n = grid.get(0).size();
        int min = 1 << 30;
        int ans = -min;
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 用于记录前缀最小值
                int i1 = min;
                // 如果不是第一行，就看看上一行这列的最小值
                if (i > 0) {
                    i1 = Math.min(i1, f[i - 1][j]);
                }
                // 如果不是第一列，就看看前一列的最小值
                if (j > 0) {
                    i1 = Math.min(i1, f[i][j - 1]);
                }
                // 更新结果，当前元素减去前缀最小值得到的值与当前答案比较
                ans = Math.max(ans, grid.get(i).get(j) - i1);
                // 更新 f[i][j] 当前元素与前缀最小值比较
                f[i][j] = Math.min(grid.get(i).get(j), i1);
            }
        }
        return ans;
    }
}
